package _02_第二季.排序;

import java.util.Arrays;

/*
    快速排序
 */
public class Quick {

    public static void sort(int[] nums){
        if(nums == null || nums.length == 0) return;
        sort(nums,0,nums.length - 1);
    }


    public static void sort(int[] nums,int lo,int hi){
        if(lo >= hi) return;

        int pivotIndex = partition(nums,lo,hi);

        sort(nums,lo,pivotIndex - 1);
        sort(nums,pivotIndex+1,hi);
    }

    private static int partition(int[] nums,int lo,int hi){
        swap(nums,lo,lo+(int)(Math.random()*(hi - lo)));
        int pivot = nums[lo];

        while(lo<hi){
            while(lo<hi){
                if(cmp(pivot,nums[hi])<0){
                    hi--;
                }else{
                    nums[lo++] = nums[hi];
                    break;
                }
            }
            while(lo<hi){
                if(cmp(pivot,nums[lo])>0){
                    lo++;
                }else{
                    nums[hi--] = nums[lo];
                    break;
                }
            }
        }
        nums[lo] = pivot;
        return lo;
    }

    private static int cmp(int i,int j){
        return i - j;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,-2,-4,6,80,45,36,21,99,66};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
